AGC 027 B Garbage Collector
けっこうおもしろい問題だったので長く考えてしまった。なにかを固定して全探索する、というのと、たぶん何回往復するか（ロボットを何台派遣するか）で固定すればいいんだろうなと思ったが、そのあとが自信持てなかった。
ロボットが必要なエネルギーを定式化したのだけれど、それをさらに変形して簡単にするとロボットの台数を固定したときの戦略が自明になる、というところまで辿りつけなかったのが悔やまれる。
問題を「ロボットを$ k台派遣して、それぞれが1往復だけしてすべてのゴミを拾ってくる」と読み替える。その場合、ゴミを拾うコストは$ NX、捨てるコストは$ kXとなる。
さてあるロボットが往復してゴミを拾う位置の降順の数列を$ pとしよう。つまり$ p = {x_10, x_7, \ldots, x_2}みたいな数列である。また$ pのサイズを$ nとする。この場合、ロボットの移動コスト$ Eは次式で計算される：
$ E = p_1 + 4(p_1 - p_2) + \cdots + (n + 1)^2p_n = 5p_1 + 5p_2 + 7p_3 + \cdots + (2n + 1)p_n
ここで、$ (i + 1)^2 - i^2 = 2i + 1に注意すること。
このことから、$ k台のロボットの間で拾うゴミを振り分けるときに、一番遠い右端の位置から順に均等に割り振っていけばコストが最小になることがわかる。つまり、右端の$ k個のゴミをそれぞれのロボットに割り振り、つぎの$ k個のゴミを割り振り、と続ければよい。最後に余った場合も均等に分けて構わない（最終的なコストはどのロボットに割り振っても等しい）。そして割り振った位置それぞれについて1つ目は$ 5それ以降は$ 2i+1をかけて足していけばよい。
ここまでで計算量は$ O(N^2)になるので、部分点はもらえるが完答には至らない。
さらに考えてみると、各$ kにおける移動コストを計算する際に累積和が使えそうなことに気付く。つまり$ k個のかたまりに含まれる位置の総和が分かれば、あとはそれに$ 2i + 1をかければよい。一見、これでも$ O(N^2)かかりそうに思えるが、各$ kに対して$ N/k回の計算でコストが計算できるので、全体としては$ \sum_{k=1}^N N/k \sim O(N \log N)となって間に合う（ちなみに調和級数をlogで押さえるのは高校でやった$ \sum_{k=1}^n 1/k \lt \int_0^n \dfrac{1}{x} dx = \log n - 1を思い出せばわかるだろう。
実際の解答ではオーバーフローに苦しめられた。とくにlong型がオーバーフローするのは初めての経験。とりあえずオーバーフローしたら無視するようにしたけれどよかったのだろうか……。
code:java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
long X = scanner.nextLong();
for (int i = 0; i < N; i++) {
}
reverse(x);
long sum = 0;
long[] xcum = new longN + 1; for (int i = 0; i < N; i++) {
}
long min = Long.MAX_VALUE;
for (int k = 1; k <= N; k++) {
long e = compute(xcum, k, N);
if (e < 0) continue;
e += k * X;
e += N * X;
if (min > e) min = e;
}
System.out.println(min);
}
private static long compute(long[] xcum, int k, int N) {
long e = 0;
long co = 5;
for (int i = 0; i < (N - 1) / k + 1; i++) {
if (i > 1) co += 2;
if (e < 0) return -1;
}
return e;
}
private static void reverse(int[] x) {
int left = 0;
int right = x.length - 1;
while (left < right) {
left++;
right--;
}
}
}